// https://leetcode.cn/problems/palindrome-linked-list/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 快慢指针找到链表中点位置
// 2. 反转链表后半部分实现对称比较
// 3. 同时遍历前后两部分验证回文性质
// 4. 不恢复链表结构节省操作时间
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include "LinkedListUtils.h"

class Solution 
{
public:
    bool isPalindrome(ListNode* head) 
    {
        if (head == nullptr) return true;

        ListNode* slow = head, *fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* prev = nullptr, *cur = slow;
        while (cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        ListNode* p1 = head, *p2 = prev;
        while (p2 != nullptr)
        {
            if (p1->val != p2->val)
            {
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        return true;
    }
};

int main()
{
    vector<int> nodes1 = {1,2,2,1};
    vector<int> nodes2 = {1,2};

    Solution sol;

    auto head1 = createLinkedList(nodes1);
    auto head2 = createLinkedList(nodes2);

    cout << (sol.isPalindrome(head1) == 1 ? "True" : "False") << endl;
    cout << (sol.isPalindrome(head2) == 1 ? "True" : "False") << endl;

    return 0;
}